package clustering;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

import preprocess.XMLDoc;
import similarity.Similarity;

public class K_MeansClustering extends Clustering
{
    public K_MeansClustering(Similarity similarity)
    {
        super(similarity);
        this.similarity = similarity;
    }

    @Override
    public List<List<XMLDoc>> cluster(List<XMLDoc> list, int count)
    {
        List<List<XMLDoc>> clu = pickRandomCenters(list, count);
        List<List<XMLDoc>> newClu = clu;
        List<XMLDoc> centers = getCenters(clu);
        System.out.println("init center:" + centers.toString());
        String keys = centers.toString();
        int times = 0;
        for (times = 0; times < MAX_CLUSTER_TIMES; times++)
        {
            clu = newClu;
            // 一次划分聚类
            for (XMLDoc doc : list)
            {
                boolean isCenter = false;
                int cluster = 0;
                double maxSimilarity = -1;
                for (int i = 0; i < centers.size(); i++)
                {
                    if (doc.equals(centers.get(i)))
                    {
                        isCenter = true;
                        break;
                    }
                    double similarity = this.similarity.calcSimilarity(doc,
                            centers.get(i));
                    if (similarity > maxSimilarity)
                    {
                        maxSimilarity = similarity;
                        cluster = i;
                    }
                }
                if (!isCenter)
                {
                    if (cluster < 0)
                    {
                        System.err.println("list size = " + list.size());
                        System.err.println("list: " + list);
                        System.err.println("centers size = " + centers.size());
                        System.err.println("centers: " + centers);
                    }
                    clu.get(cluster).add(doc);
                }
            }

            newClu = calculateCenters(clu);
            centers = getCenters(newClu);
            System.out.println("new centers:" + centers.toString());
            String newKey = centers.toString();
            if (newKey.equals(keys))
            {
                break;
            }
            else
            {
                keys = newKey;
            }
        }
        System.out.println("actual clustering times:" + (times + 1));
        return clu;
    }

    private List<XMLDoc> getCenters(List<List<XMLDoc>> lists)
    {
        List<XMLDoc> centers = new ArrayList<XMLDoc>();
        for (List<XMLDoc> l : lists)
        {
            centers.addAll(l);
        }
        return centers;
    }

    private List<List<XMLDoc>> pickRandomCenters(List<XMLDoc> list, int count)
    {
        List<List<XMLDoc>> result = new ArrayList<List<XMLDoc>>();
        int total = list.size();
        int splitter = total / count;
        Random rand = new Random(System.currentTimeMillis());
        for (int i = 0; i < count; i++)
        {
            int pos = rand.nextInt(splitter) + i * splitter;
            List<XMLDoc> l = new ArrayList<XMLDoc>();
            l.add(list.get(pos));
            result.add(l);
        }
        return result;
    }

    /*
     * remove all elements from clusters except the new centers of the cluster
     */
    private List<List<XMLDoc>> calculateCenters(List<List<XMLDoc>> lists)
    {
        List<List<XMLDoc>> result = new ArrayList<List<XMLDoc>>();
        for (List<XMLDoc> list : lists)
        {
            XMLDoc center = getCenter(list);
            List<XMLDoc> l = new ArrayList<XMLDoc>();
            l.add(center);
            result.add(l);
            // list.clear();
            // list.add(center);
        }
        return result;
    }

    /*
     * return the center of the specified cluster
     */
    public XMLDoc getCenter(List<XMLDoc> list)
    {
        XMLDoc result = null;
        double distanceSum = Double.MAX_VALUE;
        for (XMLDoc center : list)
        {
            double sum = 0;
            for (XMLDoc doc : list)
            {
                double distance = 1 - similarity.calcSimilarity(center, doc);
                sum += distance * distance;
            }
            if (sum < distanceSum)
            {
                distanceSum = sum;
                result = center;
            }
        }
        return result;
    }

    /**
     * @return the similarity
     */
    public Similarity getSimilarity()
    {
        return similarity;
    }

    /**
     * @param similarity
     *            the similarity to set
     */
    public void setSimilarity(Similarity similarity)
    {
        this.similarity = similarity;
    }

}
